package com.lizk.graph.noweight;

import com.lizk.tools.base.Checks;

import java.util.Arrays;

/**
 * 邻接矩阵(AdjacencyMatrix)
 * 适合表示稠密的图,边较多
 *   | 0 1 2 3
 * -----------
 * 0 | 0 1 0 0
 * 1 | 0 0 1 0
 * 2 | 0 0 0 1
 * 3 | 0 1 0 0
 * 以上矩阵1的位置表示对应的两个节点相连
 * 0的位置表示对应的两个节点不相连
 *
 * 邻接表(AdjacencyTable)
 * 适合表示稀疏的图,边较少
 * 0 | 1
 * 1 | 0 2 3
 * 2 | 1 3
 * 3 | 1 2
 * 第一行表示0节点跟1节点相连
 * 第二行表示1节点跟0,2,3三个节点相连
 *
 * @author lizhikui
 * @date 2020/2/15 14:25
 */
public class AdjacencyMatrix implements NoWeightGraph<Integer> {
    /*当前横向迭代的元素索引*/
    int column4Iterator;
    /*当前迭代的元素索引*/
    int row4Iterator;

    /*是否是有向图*/
    boolean directed;

    /*记录节点相连通关系的矩阵*/
    Boolean [][] g ;

    public AdjacencyMatrix(int n,boolean directed){
        g = new Boolean[n][n];
        this.directed = directed;
        for (Boolean[] booleans : g) {
            Arrays.fill(booleans, false);
        }
    }


    @Override
    public void iterator(int row){
        this.row4Iterator = row;
        this.column4Iterator = -1;
    }

    @Override
    public boolean hasNext() {
        while ( ++column4Iterator < g.length ){
            if( g[row4Iterator][column4Iterator]){
                return true;
            }
        }
        return false;
    }

    @Override
    public Integer next() {
        return column4Iterator;
    }

    @Override
    public void addEdge(int row, int col) {
        check(row,col);
        if (!hasEdge(row,col)){
            g[row][col] = true;
            if (!directed){
                g[col][row] = true;
            }
        }
    }

    @Override
    public boolean hasEdge(int row, int col) {
        check(row,col);
        return g[row][col];
    }
    private void check(int row, int col){
        Checks.checkElementIndex(row,g.length);
        Checks.checkElementIndex(col,g[row].length);
    }

}





